ABC242 C - 1111gal password

提出

code: python

n = int(input())

# 末尾に+=0,+-1の3種の数字を足してできていく

# 1と9は末尾に2種

# 1 2 3 4 5 6 7 8 9

# 11 12 21 22 23 ...

# 計算量オーバー

for i in range(1, 10):

dpi = True

解答

code: python

n = int(input())

MOD = 998244353

# dpij : 上から i 桁目まで決めて、i 桁目の数字が j である組み合わせ数（を 998244353 で割った余り)

# 末尾に足していく直感的なdp

# j=1,9 の場合はそれぞれ dpij−1、dpij+1 を省く必要があるが、この場合分けは面倒 -> 0 と 10 を設定(初期値が0のままだから影響はない)

dp = [0 * 11 for _ in range(n + 1)]

for i in range(1, 10):

dp1i = 1 # 上から1桁目の1～9はそれぞれ1通り

for i in range(1, n):

for j in range(1, 10):

dpi + 1j = (dpij - 1 + dpij + dpij + 1) % MOD

# print(dp)

# n = 2

# 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, [0, 2, 3, 3, 3, 3, 3, 3, 3, 2, 0

print(sum(dpn) % MOD)

テーマ

メモ

提出

code: python

n = int(input())

# 1 -> (1, 2), 2 -> (1, 2, 3), 3 -> (2, 3, 4), ... , 8 -> (7, 8, 9), 9 -> (8, 9)

# dp は用意しきれない

# 2 -> 2*2 + 3*7

# (11, 12), (21, 22, 23) ...

# 3 ->

# (111, 112), (121, 122, 123), (211, 212), (221, 222, 223), (232, 233, 234) ...

# 4-> 2*8 + 3*63

print(2*8 + 3*63)